//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-18


import java.util.Arrays;

public class P005_x的平方根_二分法 {

    public static void main(String[] args) {
        System.out.println(my_sqrt(98));
    }

    // 求x的平方根的整数部分
    private static int my_sqrt(int x) {
//        for (int i = 1;i < x;i++)
//            if (i * i <= x && (i+1)*(i+1) > x) return i;
//        return -1;

        // 二分查找
        int index = -1,l = 0,r = x;
        while (l <= r) {
            int mid = l + (r-l)/2;  // 找中间位置
            if (mid * mid <= x) {
                index = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return index;
    }


}
